{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Big Picture: Describing Networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Configure plotting in Jupyter\n",
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.rcParams.update({\n",
    "    'figure.figsize': (7.5, 7.5)})\n",
    "# Seed random number generator\n",
    "from numpy import random as nprand\n",
    "seed = hash(\"Network Science in Python\") % 2**32\n",
    "nprand.seed(seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data Sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "data_dir = Path('.') / 'data'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load karate club network\n",
    "G_karate = nx.karate_club_graph()\n",
    "mr_hi = 0\n",
    "john_a = 33"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load internet point of presence network\n",
    "G_internet = nx.read_graphml(data_dir / 'UAITZ' / 'Geant2012.graphml')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load Germany electrical grid\n",
    "with open(data_dir / 'mureddu2016' / '0.2' / 'branches.csv', 'rb') as f:\n",
    "    # Skip header\n",
    "    next(f)\n",
    "    # Read edgelist format\n",
    "    G_electric = nx.read_edgelist(\n",
    "        f,\n",
    "        delimiter=\"\\t\",\n",
    "        create_using=nx.Graph,\n",
    "        data=[('X', float), ('Pmax', float)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(7.5, 2.75))\n",
    "plt.subplot(1, 3, 1);\n",
    "plt.title(\"Karate\")\n",
    "nx.draw_networkx(G_karate, node_size=0, with_labels=False)\n",
    "plt.subplot(1, 3, 2)\n",
    "plt.title(\"Electric\")\n",
    "nx.draw_networkx(G_electric, node_size=0, with_labels=False)\n",
    "plt.subplot(1, 3, 3)\n",
    "plt.title(\"Internet\")\n",
    "nx.draw_networkx(G_internet, node_size=0, with_labels=False)\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diameter and Shortest Paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(nx.all_shortest_paths(G_karate, mr_hi, john_a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.shortest_path(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.shortest_path_length(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate dictionary of all shortest paths\n",
    "length_source_target = dict(nx.shortest_path_length(G_karate))\n",
    "length_source_target[0][33]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path_length_histogram(G, title=None):\n",
    "    # Find path lengths\n",
    "    length_source_target = dict(nx.shortest_path_length(G))\n",
    "    # Convert dict of dicts to flat list\n",
    "    all_shortest = sum(\n",
    "        [list(length_target.values()) for length_target in length_source_target.values()],\n",
    "        [])\n",
    "    # Calculate integer bins\n",
    "    high = max(all_shortest)\n",
    "    bins = [-0.5 + i for i in range(high + 2)]\n",
    "    # Plot histogram\n",
    "    plt.hist(all_shortest, bins=bins, rwidth=0.8)\n",
    "    plt.title(title)\n",
    "    plt.xlabel(\"Distance\")\n",
    "    plt.ylabel(\"Count\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(7.5, 2.5))\n",
    "plt.subplot(1, 3, 1)\n",
    "path_length_histogram(G_karate, title=\"Karate\")\n",
    "plt.subplot(1, 3, 2)\n",
    "path_length_histogram(G_electric, title=\"Electric\")\n",
    "plt.subplot(1, 3, 3)\n",
    "path_length_histogram(G_internet, title=\"Internet\")\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_shortest_path_length(G_internet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.diameter(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.diameter(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.diameter(G_internet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.transitivity(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.transitivity(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.transitivity(G_internet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_clustering(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_clustering(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_clustering(G_internet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resilience"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(G_internet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx.algorithms.connectivity as nxcon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nxcon.minimum_st_node_cut(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nxcon.minimum_st_edge_cut(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.node_connectivity(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.edge_connectivity(G_karate, mr_hi, john_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nxcon.minimum_node_cut(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nxcon.minimum_edge_cut(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.node_connectivity(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.node_connectivity(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.node_connectivity(G_internet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_node_connectivity(G_karate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_node_connectivity(G_electric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.average_node_connectivity(G_internet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inequality"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to plot a single histogram\n",
    "def centrality_histogram(x, title=None):\n",
    "    plt.hist(x, density=True)\n",
    "    plt.title(title)\n",
    "    plt.xlabel(\"Centrality\")\n",
    "    plt.ylabel(\"Density\")\n",
    "\n",
    "# Create a figure\n",
    "plt.figure(figsize=(7.5, 2.5))\n",
    "# Calculate centralities for each example and plot\n",
    "plt.subplot(1, 3, 1)\n",
    "centrality_histogram(\n",
    "    nx.eigenvector_centrality(G_karate).values(), title=\"Karate\")\n",
    "plt.subplot(1, 3, 2)\n",
    "centrality_histogram(\n",
    "    nx.eigenvector_centrality(G_electric, max_iter=1000).values(), title=\"Electric\")\n",
    "plt.subplot(1, 3, 3)\n",
    "centrality_histogram(\n",
    "    nx.eigenvector_centrality(G_internet).values(), title=\"Internet\")\n",
    "\n",
    "# Adjust the layout\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def entropy(x):\n",
    "    # Normalize\n",
    "    total = sum(x)\n",
    "    x = [xi / total for xi in x]\n",
    "    H = sum([-xi * math.log2(xi) for xi in x])\n",
    "    return H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy(nx.eigenvector_centrality(G_karate).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy(nx.eigenvector_centrality(G_electric, max_iter=1000).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy(nx.eigenvector_centrality(G_internet).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(x):\n",
    "    x = [xi for xi in x]\n",
    "    n = len(x)\n",
    "    gini_num = sum([sum([abs(x_i - x_j) for x_j in x]) for x_i in x])\n",
    "    gini_den = 2.0 * n * sum(x)\n",
    "    return gini_num / gini_den"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gini(nx.eigenvector_centrality(G_karate).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gini(nx.eigenvector_centrality(G_electric, max_iter=1000).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gini(nx.eigenvector_centrality(G_internet).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
